{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Meeting Rooms II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #two-pointers #prefix-sum #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #双指针 #前缀和 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minMeetingRooms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #会议室 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个会议时间安排的数组 <code>intervals</code> ，每个会议时间都会包括开始和结束的时间 <code>intervals[i] = [start<sub>i</sub>, end<sub>i</sub>]</code> ，返回 <em>所需会议室的最小数量</em> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>intervals = [[0,30],[5,10],[15,20]]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>intervals = [[7,10],[2,4]]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;=&nbsp;intervals.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= start<sub>i</sub> &lt; end<sub>i</sub> &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [meeting-rooms-ii](https://leetcode.cn/problems/meeting-rooms-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [meeting-rooms-ii](https://leetcode.cn/problems/meeting-rooms-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,30],[5,10],[15,20]]', '[[7,10],[2,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cmp_to_key\n",
    "from heapq import heappush, heappop\n",
    "\n",
    "def cmp_intvls(this: List[int], other: List[int]) -> int:\n",
    "    if this[0] < other[0] or (this[0] == other[0] and this[1] < other[1]):\n",
    "        return -1\n",
    "    if this[0] == other[0] and this[1] == other[1]:\n",
    "        return 0\n",
    "    return 1\n",
    "\n",
    "class Solution:\n",
    "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=cmp_to_key(cmp_intvls))\n",
    "\n",
    "        end_heap: List[int] = [-1]\n",
    "        for start, end in intervals:\n",
    "            if end_heap[0] <= start:\n",
    "                heappop(end_heap)\n",
    "            heappush(end_heap, end)\n",
    "        \n",
    "        return len(end_heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "# Definition for singly-linked list.\n",
    "\n",
    "\n",
    "class Heap:\n",
    "    def __init__(self, n):\n",
    "        self.length = 0\n",
    "        self.heap = [None]*(n+1)\n",
    "        self.last = 0\n",
    "\n",
    "    def insert(self, item):\n",
    "        self.length += 1\n",
    "        self.last = self.length\n",
    "        self.heap += [None]\n",
    "        self.heap[self.last] = item\n",
    "        self.bubble_up()\n",
    "\n",
    "    def bubble_up(self):\n",
    "        parent = self.last // 2\n",
    "        current = self.last\n",
    "\n",
    "        while parent > 0 and self.heap[parent] > self.heap[current]:\n",
    "            self.heap[parent], self.heap[current] = self.heap[current], self.heap[parent]\n",
    "            current, parent = parent, parent // 2\n",
    "\n",
    "    def delete(self):\n",
    "        if self.length >= 1:\n",
    "            minn = self.heap[1]\n",
    "            self.length -= 1\n",
    "            self.heap[1], self.heap[self.last] = self.heap[self.last], self.heap[1]\n",
    "            self.last -= 1\n",
    "            self.heap.pop(-1)\n",
    "            self.bubble_down()\n",
    "            return minn\n",
    "        else:\n",
    "            return None\n",
    "\n",
    "    def bubble_down(self):\n",
    "        current = 1\n",
    "        while current*2 <= self.length:\n",
    "            child = current * 2\n",
    "            if child < self.length and self.heap[child] > self.heap[child+1]:\n",
    "                child += 1\n",
    "            if self.heap[current] <= self.heap[child]:\n",
    "                break\n",
    "            else:\n",
    "                self.heap[child], self.heap[current] = self.heap[current], self.heap[child]\n",
    "\n",
    "            current = child\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
    "\n",
    "        if len(intervals) == 0:\n",
    "            return 0\n",
    "        count = 1\n",
    "        # 按开始时间排序\n",
    "        intervals.sort(key=lambda x: x[0])\n",
    "\n",
    "        # 维护一个最小堆，堆的键值是 结束时间\n",
    "        h = Heap(len(intervals))\n",
    "        h.insert(intervals[0][1])\n",
    "\n",
    "        for i in range(1, len(intervals), 1):\n",
    "            t = intervals[i]\n",
    "            e = h.delete()\n",
    "            if e <= t[0]:\n",
    "                # 可以在一个会议室\n",
    "                h.insert(t[1])\n",
    "            else:\n",
    "                count += 1\n",
    "                h.insert(e)\n",
    "                h.insert(t[1])\n",
    "\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#解题思路：运用堆和排序的思想。先通过排序将原列表进行排序。得到的一个按照开会起始时间为序的列表。然后逐个遍历，看他的起始时间，如果起始时间大于已有的会议的截止时间，那么这个会议就是可以用之前开好的办公室。所以用了堆得思想，一直把后面的起始时间拿来和堆顶比，如果堆顶大，那么就需要新开房间，将新开好的房间的结束时间放入堆，如果堆顶小，那么说明可以替代，把堆顶pop出来，然后放入新的结束时间。最后看有多少个房间就好了。\n",
    "#代码思路：sort()对列表进行排序，heapq构建堆。\n",
    "class Solution:\n",
    "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort()\n",
    "        heap = []\n",
    "        for i in intervals:\n",
    "            if not heap or i[0] < heap[0]: #如果没有房间或者已有的房间的会议都还未停止\n",
    "                heapq.heappush(heap,i[1])\n",
    "            else: #如果已有的房间的会议已经停止\n",
    "                heapq.heappop(heap)\n",
    "                heapq.heappush(heap,i[1])\n",
    "        return len(heap)\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort()\n",
    "        room = []\n",
    "        i = 0\n",
    "        while i < len(intervals):\n",
    "            if not room:\n",
    "                room.append([intervals[i]])\n",
    "            else:\n",
    "                find = False\n",
    "                l2, r2 = intervals[i]\n",
    "                for r in room:\n",
    "                    l1, r1 = r[-1]\n",
    "                    if r1 > l2:\n",
    "                        pass\n",
    "                    else:\n",
    "                        r.append(intervals[i])\n",
    "                        find = True\n",
    "                        break\n",
    "                if not find:\n",
    "                    room.append([intervals[i]])\n",
    "            i += 1\n",
    "        return len(room)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
    "\n",
    "        # If there is no meeting to schedule then no room needs to be allocated.\n",
    "        if not intervals:\n",
    "            return 0\n",
    "\n",
    "        # The heap initialization\n",
    "        free_rooms = []\n",
    "\n",
    "        # Sort the meetings in increasing order of their start time.\n",
    "        intervals.sort(key= lambda x: x[0])\n",
    "\n",
    "        # Add the first meeting. We have to give a new room to the first meeting.\n",
    "        heapq.heappush(free_rooms, intervals[0][1])\n",
    "\n",
    "        # For all the remaining meeting rooms\n",
    "        for i in intervals[1:]:\n",
    "\n",
    "            # If the room due to free up the earliest is free, assign that room to this meeting.\n",
    "            if free_rooms[0] <= i[0]:\n",
    "                heapq.heappop(free_rooms)\n",
    "\n",
    "            # If a new room is to be assigned, then also we add to the heap,\n",
    "            # If an old room is allocated, then also we have to add to the heap with updated end time.\n",
    "            heapq.heappush(free_rooms, i[1])\n",
    "\n",
    "        # The size of the heap tells us the minimum rooms required for all the meetings.\n",
    "        return len(free_rooms)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
    "        rooms = []  # 记录各会议室的结束时间\n",
    "        meetings = sorted(intervals, key=lambda x: x[0])  # 按开始时间升序\n",
    "        for meeting in meetings:\n",
    "            find = False\n",
    "            for index, end_time in enumerate(rooms):\n",
    "                # 找到满足结束时间早于当前会议开始时间的会议室，并更新会议室的时间表\n",
    "                if end_time <= meeting[0]:\n",
    "                    rooms[index] = meeting[1]\n",
    "                    find = True\n",
    "                    break\n",
    "            # 如果没找到，则新增会议室\n",
    "            if not find:\n",
    "                rooms.append(meeting[1])\n",
    "        return len(rooms)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
    "        if not intervals:\n",
    "            return 0\n",
    "        intervals.sort(key = lambda x:(x[0], x[1]))\n",
    "        heap = []\n",
    "        for interval in intervals:\n",
    "            if heap and heap[0] <= interval[0]:\n",
    "                heapq.heappop(heap)\n",
    "            heapq.heappush(heap, interval[1])\n",
    "        return len(heap)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
    "        dic = defaultdict(int)\n",
    "        for start,end in intervals:\n",
    "            dic[start] += 1\n",
    "            dic[end] -= 1\n",
    "        times = sorted(list(dic.keys()))\n",
    "        cur = 0\n",
    "        ans = 0\n",
    "        for t in times:\n",
    "            cur += dic[t]\n",
    "            ans = max(ans,cur)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
    "        #会议开始时间排序\n",
    "        intervals.sort()\n",
    "\n",
    "        rooms = [[intervals[0]]]\n",
    "        for i in range(1,len(intervals)):\n",
    "            flag = False\n",
    "            for j in rooms:\n",
    "                if intervals[i][0] >= j[-1][1]:\n",
    "                    j.append(intervals[i])\n",
    "                    flag = True\n",
    "                    break\n",
    "            if not flag:\n",
    "                rooms.append([intervals[i]])\n",
    "        return len(rooms)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
    "        import heapq\n",
    "        q = []\n",
    "        intervals.sort()\n",
    "        for i in range(len(intervals)):\n",
    "            if q and q[0] <= intervals[i][0]:\n",
    "                heapq.heappop(q)\n",
    "            heapq.heappush(q, intervals[i][1])\n",
    "        return len(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        begin = list(map(lambda x: x[0], intervals))\n",
    "        end = list(map(lambda x: x[1], intervals))\n",
    "        begin.sort()\n",
    "        end.sort()\n",
    "        ans = count = i = j = 0\n",
    "        while i < n and j < n:\n",
    "            if begin[i] < end[j]:\n",
    "                count += 1\n",
    "                i += 1\n",
    "            else:\n",
    "                count -= 1\n",
    "                j += 1\n",
    "            ans = max(ans, count)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
    "        if not intervals:\n",
    "            return 0\n",
    "        rooms = []\n",
    "        intervals.sort(key=lambda x: x[0])\n",
    "        heapq.heappush(rooms, intervals[0][1])\n",
    "        for meet in intervals[1:]:\n",
    "            if meet[0] >= rooms[0]:\n",
    "                heapq.heappop(rooms)\n",
    "            heapq.heappush(rooms, meet[1])\n",
    "        return len(rooms)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
    "        if not intervals:\n",
    "            return 0\n",
    "        n = len(intervals)\n",
    "        intervals.sort()\n",
    "        rooms = [[intervals[0][0], intervals[0][1]]]\n",
    "        for i in range(1, n):\n",
    "            found_room = False\n",
    "            for room in rooms:\n",
    "                if room[0] <= intervals[i][0] < room[1]:\n",
    "                    continue\n",
    "                room[1] = intervals[i][1]\n",
    "                found_room = True\n",
    "                break\n",
    "            if not found_room:\n",
    "                rooms.append([intervals[i][0], intervals[i][1]])\n",
    "        return len(rooms)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
    "        # non-overlap dividing\n",
    "        if len(intervals) == 1:\n",
    "            return 1\n",
    "        \n",
    "        # 同一时间开会的最大数量, i.e. 最大重叠数量\n",
    "        # time_meeting = [0] * (10**6)\n",
    "        # for intev in intervals:\n",
    "        #     # this step time consuming\n",
    "        #     for time in range(intev[0], intev[1]):\n",
    "        #         time_meeting[time] += 1\n",
    "        # return max(time_meeting)\n",
    "\n",
    "        # 区间长度问题，依次遍历每个取值比较耗时，针对区间端点比较节省时间！！！\n",
    "        start = [i[0] for i in intervals]\n",
    "        end = [i[1] for i in intervals]\n",
    "        start = sorted(start)\n",
    "        end = sorted(end)\n",
    "        ans = 0\n",
    "        count = 0\n",
    "        i , j = 0, 0\n",
    "        while i < len(intervals) and j < len(intervals):\n",
    "            if start[i] < end[j]:\n",
    "                count += 1\n",
    "                i += 1\n",
    "            else:\n",
    "                count -= 1\n",
    "                j += 1\n",
    "            ans = max(ans, count)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
    "        intervals_ascend = sorted(intervals, key=lambda s: s[0])\n",
    "        min_heap = []\n",
    "        for i in range(len(intervals_ascend)):\n",
    "            if len(min_heap)==0: self.push(min_heap,intervals_ascend[i][1])\n",
    "            else:\n",
    "                if intervals_ascend[i][0]>=min_heap[0]: self.update(min_heap,intervals_ascend[i][1])\n",
    "                else: self.push(min_heap,intervals_ascend[i][1])\n",
    "        return len(min_heap)\n",
    "    def push(self,min_heap,val):\n",
    "        if len(min_heap)==0: min_heap.append(val)\n",
    "        else:\n",
    "            min_heap.append(val)\n",
    "            cur_ind = len(min_heap)-1\n",
    "            par_ind = floor((cur_ind-1)/2)\n",
    "            while par_ind>=0:\n",
    "                if min_heap[par_ind]>min_heap[cur_ind]:\n",
    "                    t = min_heap[par_ind]\n",
    "                    min_heap[par_ind] = min_heap[cur_ind]\n",
    "                    min_heap[cur_ind] =t\n",
    "                    cur_ind = par_ind\n",
    "                    par_ind = floor((cur_ind-1)/2)\n",
    "                else: break\n",
    "    def update(self,min_heap,val):\n",
    "        min_heap[0] = val\n",
    "        max_ind = len(min_heap)-1\n",
    "        par_ind = 0\n",
    "        l_ind = (par_ind+1)*2-1\n",
    "        r_ind = (par_ind+1)*2\n",
    "        while l_ind<=max_ind:\n",
    "            if r_ind>max_ind:\n",
    "                if min_heap[par_ind]>min_heap[l_ind]:\n",
    "                    t = min_heap[par_ind]\n",
    "                    min_heap[par_ind] = min_heap[l_ind]\n",
    "                    min_heap[l_ind] = t\n",
    "                    break;\n",
    "                else: break\n",
    "            else:\n",
    "                if min_heap[l_ind]<min_heap[r_ind]: m_ind = l_ind\n",
    "                else: m_ind = r_ind\n",
    "                if min_heap[par_ind]>min_heap[m_ind]:\n",
    "                    t = min_heap[par_ind]\n",
    "                    min_heap[par_ind] = min_heap[m_ind]\n",
    "                    min_heap[m_ind] = t\n",
    "                    par_ind = m_ind\n",
    "                    l_ind = (par_ind+1)*2-1\n",
    "                    r_ind = (par_ind+1)*2\n",
    "                else: break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
    "        # intervals.sort(key=lambda x: (x[0], x[1]))\n",
    "        # # print(intervals)\n",
    "        # result = list()\n",
    "        # for it in intervals:\n",
    "        #     for x in result:\n",
    "        #         if it[0] >= x[-1][1]:\n",
    "        #             x.append(it)\n",
    "        #             break\n",
    "        #     else:\n",
    "        #         result.append([it])\n",
    "        # return len(result)\n",
    "        hp = list()\n",
    "        intervals.sort()\n",
    "        for it in intervals:\n",
    "            if not hp:\n",
    "                heappush(hp, it[1])\n",
    "            else:\n",
    "                if it[0] >= hp[0]:\n",
    "                    heapreplace(hp, it[1])\n",
    "                else:\n",
    "                    heappush(hp, it[1])\n",
    "        return len(hp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort()\n",
    "    \n",
    "        p=intervals[0]\n",
    "        que=[]\n",
    "        heapq.heappush(que,(p[1],p[0]))\n",
    "        ans=1\n",
    "        for i in range(1,len(intervals)):\n",
    "            start,end=intervals[i]\n",
    "            while(que and que[0][0]<=start):\n",
    "                heappop(que)\n",
    "            heappush(que,(end,start))\n",
    "            # print(que)\n",
    "            ans=max(ans,len(que))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort()\n",
    "        rooms = [0]\n",
    "        for i in range(len(intervals)):\n",
    "            min_time = min(rooms)\n",
    "            room_numer = rooms.index(min_time)\n",
    "            if intervals[i][0] >= min_time:\n",
    "                rooms[room_numer] = intervals[i][1]\n",
    "            else:\n",
    "                rooms.append(intervals[i][1])\n",
    "        return len(rooms)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        start = []\n",
    "        end = []\n",
    "        for intervals in intervals:\n",
    "            start.append(intervals[0])\n",
    "            end.append(intervals[1])\n",
    "        start.sort()\n",
    "        end.sort()\n",
    "        room = 0\n",
    "        left = 0\n",
    "        for i in range(n):\n",
    "            room += 1\n",
    "            if end[left] <= start[i]:\n",
    "                left += 1\n",
    "                room -= 1\n",
    "        return room"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x: (x[0], x[1]))\n",
    "        ans = []\n",
    "        for interval in intervals:\n",
    "            if not ans:\n",
    "                heapq.heappush(ans, interval[1])\n",
    "            else:\n",
    "                cur = heapq.heappop(ans)\n",
    "                if cur <= interval[0]:\n",
    "                    heapq.heappush(ans, interval[1])\n",
    "                else:\n",
    "                    heapq.heappush(ans, interval[1])\n",
    "                    heapq.heappush(ans, cur)\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x: (x[0], x[1]))\n",
    "        h = []\n",
    "        for interval in intervals:\n",
    "            if not h or interval[0] < h[0]:\n",
    "                heapq.heappush(h, interval[1])\n",
    "            elif interval[0] >= h[0]:\n",
    "                heapq.heappop(h)\n",
    "                heapq.heappush(h, interval[1])\n",
    "        return len(h)\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mremove(self,px,py,intervals):\n",
    "        ans = []\n",
    "        prev = []\n",
    "        for i in range(len(intervals)):\n",
    "            x = intervals[i][0]\n",
    "            y = intervals[i][1]\n",
    "            print(f'x:{x}, y:{y}')\n",
    "            if(py <= x): # compatible\n",
    "                ans.append([x,y])\n",
    "                px = x\n",
    "                py = y\n",
    "            else: # incompatible\n",
    "                prev.append([x,y])\n",
    "        return ans, prev\n",
    "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
    "        intervals = sorted(intervals)\n",
    "        i = 0\n",
    "        k = 0\n",
    "        while(len(intervals) > 0):\n",
    "            print(intervals)\n",
    "            x = intervals[i][0]\n",
    "            y = intervals[i][1]\n",
    "            _, intervals = self.mremove(x,y,intervals[i+1:])\n",
    "            k += 1\n",
    "        return k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
    "        times = [(i[0],1) for i in intervals]+[(i[1],-1) for i in intervals]\n",
    "        times.sort()\n",
    "        cur, ans = 0, 0\n",
    "        for t in times:\n",
    "            cur += t[1]\n",
    "            ans = max(cur, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
    "        events = [(iv[0], 1) for iv in intervals] + [(iv[1], -1) for iv in intervals]\n",
    "        events.sort()\n",
    "        ans = cur = 0\n",
    "        for _, e in events:\n",
    "            cur += e\n",
    "            ans = max(ans, cur)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
    "        time_list = []\n",
    "        for interval in intervals:\n",
    "            time_list.append([interval[0], 1])\n",
    "            time_list.append([interval[1], -1])\n",
    "        time_list = sorted(time_list, key = lambda x: x[1])\n",
    "        time_list = sorted(time_list, key = lambda x: x[0])\n",
    "        ans = 0\n",
    "        max_cnt = 0\n",
    "        for i in time_list:\n",
    "            if i[1] == 1: ans += 1\n",
    "            else: ans -= 1\n",
    "            max_cnt = max(max_cnt, ans)\n",
    "        return max_cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
    "        '''\n",
    "        把会议开始、结束都当做事件，不停+1 -1，取最大值即可\n",
    "        '''\n",
    "        events = []\n",
    "        for start, end in intervals:\n",
    "            events.extend([start, -end])\n",
    "        # 顺序要保证同一时间的结束事件要排在开始事件前面\n",
    "        events.sort(key=lambda x: (abs(x), x))\n",
    "\n",
    "        ret = 0\n",
    "        count = 0\n",
    "        for e in events:\n",
    "            if e >= 0:\n",
    "                count += 1\n",
    "            else:\n",
    "                count -= 1\n",
    "            ret = max(ret, count)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
    "        '''\n",
    "        把会议开始、结束都当做事件，不停+1 -1，取最大值即可\n",
    "        '''\n",
    "        events = []\n",
    "        for start, end in intervals:\n",
    "            events.extend([start, -end])\n",
    "        # 顺序要保证同一时间的结束事件要排在开始事件前面\n",
    "        events.sort(key=lambda x: (abs(x), x))\n",
    "\n",
    "        ret = 0\n",
    "        count = 0\n",
    "        for e in events:\n",
    "            if e >= 0:\n",
    "                count += 1\n",
    "            else:\n",
    "                count -= 1\n",
    "            ret = max(ret, count)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
    "        queue = []\n",
    "        for x in intervals:\n",
    "            queue.append((x[0], 1))\n",
    "            queue.append((x[1], -1))\n",
    "        \n",
    "        queue.sort(key=lambda x:(x[0], x[1]))\n",
    "        count = 0\n",
    "        max_count = 0\n",
    "        for item in queue:\n",
    "            count += item[1]\n",
    "            max_count = max(max_count, count)\n",
    "        \n",
    "        return max_count\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
